1029C - Maximal Intersection - CodeForces Solution

// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
// Written by Ilia Rahbar

// #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target ("abm,bmi,bmi2,tbm,avx2")

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define sz(x) int(x.size())
#define ai(x) array <int, x>
#define be(x) x.begin(), x.end()
#define pb push_back
#define el '\n'
#define sp ' '
#define fi first 
#define se second

const int M = 1e9 + 7, N = 1e6 + 100;

int n, ans = 0, x, y;

ai(2) a[N], l[N], r[N];

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i][0] >> a[i][1];

    l[0] = a[0];

    for (int i = 1; i < n; i++)
        l[i][0] = max(l[i-1][0], a[i][0]), l[i][1] = min(l[i-1][1], a[i][1]);

    r[n-1] = a[n-1];

    for (int i = n-2; i >= 0; i--)
        r[i][0] = max(r[i+1][0], a[i][0]), r[i][1] = min(r[i+1][1], a[i][1]);

    for (int i = 1; i < n-1; i++)
    {
        x = max(r[i+1][0], l[i-1][0]);
        y = min(r[i+1][1], l[i-1][1]);

        ans = max(ans, y - x);
    }

    cout << max(ans, max(r[1][1] - r[1][0], l[n-2][1] - l[n-2][0]));
}